//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 5419 👎 0


package leetcode.editor.cn;

import java.util.HashMap;

/**
 * 最长回文子串
 * @date 2022-07-08 09:22:39
 */
class P5_LongestPalindromicSubstring{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P5_LongestPalindromicSubstring().new Solution();
		 System.out.println(solution.longestPalindrome1("ba"));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
		/**
		 * 暴力解法
		 */
		if(s.length() < 2){
			return s;
		}
		int maxlen = 0;
		int begin = 0;
		char[] chars = s.toCharArray();
		for (int i = 0; i < s.length() - 1; i++) {
			for (int j = i+maxlen; j < s.length(); j++) {
				if(isPalindrome(chars,i,j) && j-i+1>maxlen){
					maxlen = j-i+1;
					begin = i;
				}
			}
		}
		return s.substring(begin,begin+maxlen);
    }
	public boolean isPalindrome(char[] chars,int left,int right){
		while(left<=right){
			if(chars[left] != chars[right]){
				return false;
			}
			left++;
			right--;
		}
		return true;
	}
	public String longestPalindrome1(String s) {
		/**
		 * 动态规划解决
		 */
		int len = s.length();
		if(len<2){
			return s;
		}
		int maxlen = 1;//记录回文子串的最大长度
		int begin = 0;//记录回文子串的起始位置
		char[] chars = s.toCharArray();
		boolean[][] dp = new boolean[len][len];//dp[i][j]表示i到j是否是回文子串，左闭右闭
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;
		}
		for (int j = 1; j < len; j++) {
			for (int i = 0; i < j; i++) {
				if(chars[i] != chars[j]){
					dp[i][j] = false;
				}else{
					if(j-i<2){
						dp[i][j] = true;
					}else{
						dp[i][j] = dp[i+1][j-1];
					}
				}
				if(dp[i][j] && j-i+1>maxlen){
					maxlen = j-i+1;
					begin = i;
				}
			}
		}
		return s.substring(begin,begin+maxlen);
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
